#include "orderer.h"
#include <stdio.h>


void bubble_sort(int* array, const int length) {
  
  register int last_index, buble_index;
  int temp;
  int* ordered_array = array;
  
  for (last_index = length - 1; last_index > 0; --last_index) {
    
    array = ordered_array;
    
    for (buble_index = 0; buble_index < last_index; ++buble_index) {
      
      if (*array > *(array + 1)) {
	temp = *array;
	*array = *(array + 1);
	*(array + 1) = temp;
      }
      ++array;
    }
  }
  
  array = ordered_array;
}


void selection_sort(int* array, const int length) {
  
  register int index, min_index;
  int temp, min_temp, min_temp_index;
  
  for (index = 0; index < length - 1; ++index) {
    
    min_temp = *(array + index);
    min_temp_index = index;
    
    // Looking for the min element between [index, length]
    for (min_index = index + 1; min_index < length; ++min_index)      
      if (*(array + min_index) < min_temp) {
	min_temp = *(array + min_index);
	min_temp_index = min_index;
      }
    // Changing the min element by the first element
    if (min_temp < *(array + index)) {
      temp = *(array + index);
      *(array + index) = min_temp;
      *(array + min_temp_index) = temp;
    }
  }  
}


void insertion_sort(int* array, const int length) {
  
  register int index, retro_index;
  int candidate;
  
  for (index = 1; index < length; ++index) {
    candidate = array[index];
    retro_index = index - 1;
    
    while (candidate < array[retro_index]) {
      array[retro_index + 1] = array[retro_index];
      --retro_index;
      if (retro_index < 0) break; 
    }
    
    array[retro_index + 1] = candidate;
  }
}


void shell_sort(int* array, const int length) {
  
  register int gap, index_array, gap_candidate, index_gap_array;
  
  // Computing the gap 
  gap = 1; while (gap < length) gap = 3 * gap + 1;
  
  while (gap) {
    
    gap = gap / 3;
    
    for (index_array = gap; index_array < length; ++index_array) {
      
      gap_candidate = array[index_array];
      
      for (index_gap_array = index_array - gap; gap_candidate < array[index_gap_array] && index_gap_array >= 0; 
	   index_gap_array -= gap) {
	array[index_gap_array + gap] = array[index_gap_array];
      }
      
      array[index_gap_array + gap] = gap_candidate;
    }
  }
}


/*
 * This is the function that implements the quick sort algorithm.
 */
void _quick(int* array, const int left, const int right) {
  
  register int lim_inf, lim_sup, partition_element, temp;
  
  partition_element = array[(left + right)/2];  
  lim_inf = left;
  lim_sup = right;
  
  do { 
    while (array[lim_inf] < partition_element && lim_inf < right) ++lim_inf;
    while (array[lim_sup] > partition_element && lim_sup > left) --lim_sup;
    
    if (lim_inf <= lim_sup) {
      temp = array[lim_inf];
      array[lim_inf] = array[lim_sup];
      array[lim_sup] = temp;
      ++lim_inf; --lim_sup;
    }
  } while (lim_inf <= lim_sup);
  
  if (lim_inf < right) _quick(array, lim_inf, right);
  if (lim_sup > left) _quick(array, left, lim_sup);
}

void quick_sort(int* array, const int length) {
  _quick(array, 0, length - 1);
}


void build_heap(const int left, const int right, int* array) {
  
  register int index, val_aux, index_aux, array_modified;
  
  do {
    
    array_modified = 0;
    
    for (index = left; index >= 0; --index) {
      
      index_aux = 0;
      
      if (array[index] < array[2 * index]) {
	index_aux = 2 * index;
      }
      else if (array[index] < array[2 * index + 1]) {
	index_aux = 2 * index + 1;
      }
      
      if (index_aux && index_aux <= right) {
	val_aux = array[index];
	array[index] = array[index_aux];
	array[index_aux] = val_aux;
	array_modified = 1;
      }
    }
  } while (array_modified);
    
}

void heap_sort(int* array, const int length) {
  
  register int left_index, right_index, max_val;
  
  for (right_index = length - 1; right_index > 0; --right_index) {
    
    left_index = right_index / 2;
    build_heap(left_index, right_index, array);
    
    max_val = array[0];
    array[0] = array[right_index];
    array[right_index] = max_val;
  }

}


